package src.tree;

/**
 * 线段树
 */
public class SegmentTree<E> {

    private E[] data;
    private E[] tree;
    private Merger<E> merger;

    public SegmentTree(E[] arr, Merger<E> merger){
        this.merger = merger;
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        tree = (E[]) new Object[4* arr.length];
        build(0, 0, data.length - 1);
    }

    /**
     * 创建一颗线段树
     * @param treeIndex 根节点
     * @param l 左边界
     * @param r 右边界
     */
    private void build(int treeIndex, int l, int r){
        // 递归到低的情况
        if (l == r) {
            tree[treeIndex] = data[l];
            return ;
        }
        int left = leftChild(treeIndex);
        int right = rightChild(treeIndex);
        int mid = l + (r - l) / 2;
        build(left, l, mid);
        build(right, mid + 1, r);
        tree[treeIndex] = merger.merge(tree[left], tree[right]);
    }

    public E query(int l, int r) {
        if (l < 0 || r < 0|| l > data.length || r > data.length || l > r ) {
            throw new IllegalArgumentException("Index out of range");
        }
        return query(0, 0, data.length - 1, l, r);
    }

    /**
     * 在以index节点(l,r)为根的线段树中，查询ql~qr的数据
     * @param index 节点信息
     * @param l 节点信息：左边界
     * @param r 节点信息：右边界
     * @param ql 查询范围：左边界
     * @param qr 查询范围：右边界
     * @return
     */
    private E query(int index, int l, int r, int ql, int qr){
        // 递归到底的情况，查找的区间等于当前节点的区间
        if (l == ql && r == qr) {
            return tree[index];
        }
        int mid = l + (r - l) / 2;
        int left = leftChild(index);
        int right = rightChild(index);
        // 查找左边界大于了 左子树的右边界，则去右子树找
        if (ql >= mid + 1) {
            return query(right, mid + 1, r, ql, qr);
        }
        else if(qr <= mid){
            return query(left, l, mid, ql, qr);
        }else{
            E leftRes = query(left, l, mid, ql, mid);
            E rightRes = query(right, mid + 1, r, mid + 1, qr);
            return merger.merge(leftRes, rightRes);
        }

    }

    /**
     * 更新操作
     * @param index
     * @param e
     */
    public void set(int index, E e){
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("Index out of range.");
        }
        data[index] = e;
        set(0, 0, data.length - 1, index, e);
    }
    /**
     * 线段树的更新
     * @param treeIndex 根节点索引
     * @param l 根节点信息：左边界
     * @param r 根节点信息：右边界
     * @param index 更新节点的索引
     * @param e 更新的值
     */
    private void set(int treeIndex, int l, int r, int index, E e){
        if (l == r) {
            tree[treeIndex] = e;
            return ;
        }
        int mid = l + (r - l) / 2;
        int left = leftChild(treeIndex);
        int right = rightChild(treeIndex);
        if (index >= mid + 1) {
            set(right, mid + 1, r, index, e);
        }else{
            set(left, l, mid, index, e);
        }
        tree[treeIndex] = merger.merge(tree[left], tree[right]);
    }

    public E get(int index){
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("Index out of range.");
        }
        return data[index];
    }

    public int getSize(){
        return data.length;
    }

    private int leftChild(int index){
        return 2 * index + 1;
    }

    private int rightChild(int index){
        return 2 * index + 2;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append('[');
        for (int i = 0; i < tree.length; i++) {
            if (tree[i] != null) {
                res.append(tree[i]);
            }else{
                res.append("null");
            }
            if (i != tree.length - 1) {
                res.append(", ");
            }
        }
        res.append("]");
        return res.toString();
    }




}